package com.shm.leetcode;

/**
 * 689. 三个无重叠子数组的最大和
 * 给你一个整数数组 nums 和一个整数 k ，找出三个长度为 k 、互不重叠、且 3 * k 项的和最大的子数组，并返回这三个子数组。
 *
 * 以下标的数组形式返回结果，数组中的每一项分别指示每个子数组的起始位置（下标从 0 开始）。如果有多个结果，返回字典序最小的一个。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [1,2,1,2,6,7,5,1], k = 2
 * 输出：[0,3,5]
 * 解释：子数组 [1, 2], [2, 6], [7, 5] 对应的起始下标为 [0, 3, 5]。
 * 也可以取 [2, 1], 但是结果 [1, 3, 5] 在字典序上更大。
 * 示例 2：
 *
 * 输入：nums = [1,2,1,2,1,2,1,2,1], k = 2
 * 输出：[0,2,4]
 *
 *
 * 提示：
 *
 * 1 <= nums.length <= 2 * 104
 * 1 <= nums[i] < 216
 * 1 <= k <= floor(nums.length / 3)
 *
 * 要计算三个无重叠子数组的最大和，我们可以枚举第三个子数组的位置，同时维护前两个无重叠子数组的最大和及其位置。
 *
 * 要计算两个无重叠子数组的最大和，我们可以枚举第二个子数组的位置，同时维护第一个子数组的最大和及其位置。
 *
 * 因此，我们首先来解决单个子数组的最大和问题，然后解决两个无重叠子数组的最大和问题，最后解决三个无重叠子数组的最大和问题。
 *
 * 作者：LeetCode-Solution
 * 链接：https://leetcode-cn.com/problems/maximum-sum-of-3-non-overlapping-subarrays/solution/san-ge-wu-zhong-die-zi-shu-zu-de-zui-da-4a8lb/
 * @author SHM
 */
public class MaxSumOfThreeSubarrays {
    /**
     * 前言一：单个子数组的最大和
     * 我们用滑动窗口来解决这一问题。
     *
     * 滑动窗口是数组/字符串问题中常用的抽象概念。窗口通常是指在数组/字符串中由开始和结束索引定义的一系列元素的集合，即闭区间 [i,j][i,j]。而滑动窗口是指可以将两个边界向某一方向「滑动」的窗口。例如，我们将 [i,j][i,j] 向右滑动 11 个元素，它将变为 [i+1,j+1][i+1,j+1]。
     *
     * 设 \textit{sum}_1sum
     * 1
     * ​
     *   为大小为 kk 的窗口的元素和，当窗口从 [i-k+1,i][i−k+1,i] 向右滑动 11 个元素后，\textit{sum}_1sum
     * 1
     * ​
     *   增加了 \textit{nums}[i+1]nums[i+1]，减少了 \textit{nums}[i-k+1]nums[i−k+1]。据此我们可以 O(1)O(1) 地计算出向右滑动 11 个元素后的窗口的元素和。
     *
     * 我们从 [0,k-1][0,k−1] 开始，不断地向右滑动窗口，直至窗口右端点到达数组末尾时停止。统计这一过程中的 \textit{sum}_1sum
     * 1
     * ​
     *   的最大值（记作 \textit{maxSum}_1maxSum
     * 1
     * ​
     *  ）及其对应位置。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/maximum-sum-of-3-non-overlapping-subarrays/solution/san-ge-wu-zhong-die-zi-shu-zu-de-zui-da-4a8lb/
     * @param nums
     * @param k
     * @return
     */
    public int[] maxSumOfOneSubarrays(int[] nums, int k) {
        int[] ans = new int[1];
        int sum = 0,maxSum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum+=nums[i];
            if (i>=k-1){
                if (sum>maxSum){
                    maxSum = sum;
                    ans[0] = i-k+1;
                }
                sum-=nums[i-k+1];
            }
        }
        return ans;
    }

    /**
     * 前言二：两个无重叠子数组的最大和
     * 我们使用两个大小为 kk 的滑动窗口。设 \textit{sum}_1sum
     * 1
     * ​
     *   为第一个滑动窗口的元素和，该滑动窗口从 [0,k-1][0,k−1] 开始；\textit{sum}_2sum
     * 2
     * ​
     *   为第二个滑动窗口的元素和，该滑动窗口从 [k,2k-1][k,2k−1] 开始。
     *
     * 我们同时向右滑动这两个窗口，并维护 \textit{sum}_1sum
     * 1
     * ​
     *   的最大值 \textit{maxSum}_1maxSum
     * 1
     * ​
     *   及其对应位置。每次滑动时，计算当前 \textit{maxSum}_1maxSum
     * 1
     * ​
     *   与 \textit{sum}_2sum
     * 2
     * ​
     *   之和。统计这一过程中的 \textit{maxSum}_1+\textit{sum}_2maxSum
     * 1
     * ​
     *  +sum
     * 2
     * ​
     *   的最大值（记作 \textit{maxSum}_{12}maxSum
     * 12
     * ​
     *  ）及其对应位置。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/maximum-sum-of-3-non-overlapping-subarrays/solution/san-ge-wu-zhong-die-zi-shu-zu-de-zui-da-4a8lb/
     * @param nums
     * @param k
     * @return
     */
    public int[] maxSumOfTwoSubarrays(int[] nums, int k) {
        int[] ans = new int[2];
        int sum1 = 0,maxSum1 = 0,maxSum1Idx = 0;
        int sum2 = 0,maxSum12 = 0;
        for (int i = k; i < nums.length; i++) {
            sum1 +=nums[i-k];
            sum2 +=nums[i];
            if(i>k*2-1){
                if (sum1>maxSum1){
                    maxSum1=sum1;
                    maxSum1Idx = i-k*2+1;
                }
                if (maxSum1+sum2>maxSum12){
                    maxSum12 = maxSum1+sum2;
                    ans[0] = maxSum1Idx;
                    ans[1] = i-k+1;
                }
                sum1-=nums[i-2*k+1];
                sum2-=nums[i-k+1];
            }
        }
        return ans;
    }

    /**
     * 方法一：滑动窗口
     * 回到本题，我们使用三个大小为 kk 的滑动窗口。设 \textit{sum}_1sum
     * 1
     * ​
     *   为第一个滑动窗口的元素和，该滑动窗口从 [0,k-1][0,k−1] 开始；\textit{sum}_2sum
     * 2
     * ​
     *   为第二个滑动窗口的元素和，该滑动窗口从 [k,2k-1][k,2k−1] 开始；\textit{sum}_3sum
     * 3
     * ​
     *   为第三个滑动窗口的元素和，该滑动窗口从 [2k,3k-1][2k,3k−1] 开始。
     *
     * 我们同时向右滑动这三个窗口，按照前言二的方法并维护 \textit{maxSum}_{12}maxSum
     * 12
     * ​
     *   及其对应位置。每次滑动时，计算当前 \textit{maxSum}_{12}maxSum
     * 12
     * ​
     *   与 \textit{sum}_3sum
     * 3
     * ​
     *   之和。统计这一过程中的 \textit{maxSum}_{12}+\textit{sum}_3maxSum
     * 12
     * ​
     *  +sum
     * 3
     * ​
     *   的最大值及其对应位置。
     *
     * 对于题目要求的最小字典序，由于我们是从左向右遍历的，并且仅当元素和超过最大元素和时才修改最大元素和，从而保证求出来的下标列表是字典序最小的。
     *
     * 方法一：滑动窗口
     * 回到本题，我们使用三个大小为 kk 的滑动窗口。设 \textit{sum}_1sum
     * 1
     * ​
     *   为第一个滑动窗口的元素和，该滑动窗口从 [0,k-1][0,k−1] 开始；\textit{sum}_2sum
     * 2
     * ​
     *   为第二个滑动窗口的元素和，该滑动窗口从 [k,2k-1][k,2k−1] 开始；\textit{sum}_3sum
     * 3
     * ​
     *   为第三个滑动窗口的元素和，该滑动窗口从 [2k,3k-1][2k,3k−1] 开始。
     *
     * 我们同时向右滑动这三个窗口，按照前言二的方法并维护 \textit{maxSum}_{12}maxSum
     * 12
     * ​
     *   及其对应位置。每次滑动时，计算当前 \textit{maxSum}_{12}maxSum
     * 12
     * ​
     *   与 \textit{sum}_3sum
     * 3
     * ​
     *   之和。统计这一过程中的 \textit{maxSum}_{12}+\textit{sum}_3maxSum
     * 12
     * ​
     *  +sum
     * 3
     * ​
     *   的最大值及其对应位置。
     *
     * 对于题目要求的最小字典序，由于我们是从左向右遍历的，并且仅当元素和超过最大元素和时才修改最大元素和，从而保证求出来的下标列表是字典序最小的。
     *
     * 复杂度分析
     *
     * 时间复杂度：O(n)O(n)，其中 nn 是数组 \textit{nums}nums 的长度。
     *
     * 空间复杂度：O(1)O(1)。我们只需要常数空间来存放若干变量。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/maximum-sum-of-3-non-overlapping-subarrays/solution/san-ge-wu-zhong-die-zi-shu-zu-de-zui-da-4a8lb/
     * @param nums
     * @param k
     * @return
     */
    public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
        int[] ans = new int[3];
        int sum1 = 0,maxSum1 = 0,maxSum1Idx = 0;
        int sum2 = 0,maxSum12 = 0,maxSum12Idx1 = 0,maxSum12Idx2 = 0;
        int sum3 =0,maxSum123=0;
        for (int i = 2*k; i < nums.length; i++) {
            sum1+=nums[i-2*k];
            sum2+=nums[i-k];
            sum3+=nums[i];
            if (i>=3*k-1){
                if(sum1>maxSum1){
                    maxSum1=sum1;
                    maxSum1Idx=i-3*k+1;
                }
                if (maxSum1+sum2>maxSum12){
                    maxSum12 = maxSum1+sum2;
                    maxSum12Idx1 = maxSum1Idx;
                    maxSum12Idx2 = i-2*k+1;
                }
                if (maxSum12+sum3>maxSum123){
                    maxSum123=maxSum12+sum3;
                    ans[2] = i-k+1;
                    ans[1]=maxSum12Idx2;
                    ans[0]=maxSum12Idx1;
                }
                sum1-=nums[i-3*k+1];
                sum2-=nums[i-2*k+1];
                sum3-=nums[i-k+1];
            }
        }
        return ans;
    }
}
